UVa/10047 - The monocycle/10047.cpp

   1 #include <iostream>
   2 #include <queue>
   3
   4 using namespace std;
   5
   6 int di[] = {-1, +0, +1, +0 };
   7 int dj[] = {+0, +1, +0, -1 };
   8 enum {green, black, red, blue, white};
   9 enum {up, right, down, left};
  10
  11 char g[30][30];
  12
  13 struct state{
  14     int i, j, color, dir, w;
  15     state(){}
  16     state(int I, int J, int C, int D, int W) : i(I), j(J), color(C), dir(D), w(W) {}
  17 };
  18
  19 bool visited[30][30][10][10];
  20
  21 int main(){
  22   //freopen("in.txt", "r", stdin);
  23     int rows, cols, C=1;
  24     while (cin >> rows >> cols && rows && cols){
  25         if (C > 1) cout << endl;
  26         pair<int, int> start, end;
  27         for (int i=0; i<rows; ++i){
  28             for (int j=0; j<cols; ++j){
  29                 char c; cin >> g[i][j];
  30                 if (g[i][j] == 'S') start = make_pair(i,j);
  31                 if (g[i][j] == 'T') end = make_pair(i, j);
  32             }
  33         }
  34
  35         cout << "Case #" << C++ << endl;
  36
  37         memset(visited, 0, sizeof visited);
  38         queue<state> q;
  39         q.push(state(start.first, start.second, green, up, 0));
  40         bool solved = false;
  41         while (q.size()){
  42               int i = q.front().i, j = q.front().j, c = q.front().color, d = q.front().dir, w = q.front().w;
  43               q.pop();
  44
  45               if (i == end.first && j == end.second && c == green){
  46                  cout << "minimum time = " << w << " sec" << endl;
  47                  solved = true;
  48                  break;
  49               }
  50
  51               if ((0 <= i && i < rows && 0 <= j && j < cols) == false) continue;
  52               if (g[i][j] == '#') continue;
  53               if (visited[i][j][c][d]) continue;
  54               visited[i][j][c][d] = true;
  55
  56               q.push(state(i, j, c, (d+1)%4, w+1 ));
  57               q.push(state(i, j, c, (d+3)%4, w+1 ));
  58               q.push(state(i + di[d], j + dj[d], (c+1)%5, d, w+1));
  59         }
  60         if (!solved) cout << "destination not reachable" << endl;
  61     }
  62     return 0;
  63 }